package 剑指offer;

/**
 * @description: 给定一个整形数组arr，已知其中所有的值都是非负的，
 * 将这个数组看作一个容器，请返回容器能装多少水。
 * <p>
 * 输入：[3,1,2,5,2,4]
 * 输出：5
 * @author: ywk
 * @date: 2021-02-16
 */
public class 容器盛水问题 {
    /**
     * max water
     *
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    static public long maxWater(int[] arr) {
        // write code here
        long sum = 0;
        int[] leftArr = new int[arr.length];
        int[] rightArr = new int[arr.length];
        int left = arr[0], right = arr[arr.length - 1];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > left) {
                left = arr[i];
            }
            leftArr[i] = left;
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] > right) {
                right = arr[i];
            }
            rightArr[i] = right;
        }
        for (int i = 0; i < arr.length; i++) {
            int max = Math.min(leftArr[i], rightArr[i]);
            sum += max - arr[i];
        }
        return sum;
    }

    static public long maxWater2(int[] arr) {
        int leftMax = arr[0], rightMax = arr[arr.length - 1];
        int left = 0, right = arr.length - 1;
        long sum = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, arr[left]);
            rightMax = Math.max(rightMax, arr[right]);
            if (leftMax < rightMax) {
                sum += leftMax - arr[left];
                left++;
            }else{
                sum += rightMax - arr[right];
                right--;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(maxWater2(new int[]{1, 2, 3, 0, 1}));
    }
}
